/*题目分析：
* 回文的特点：1、链表前一半与后一半元素相同，顺序相反（偶数个元素）
* 2、除中间元素外，前半段元素与后半段元素相同，顺序相反
* 解法设想：比较元素的大小与顺序
* 1、指针法：分别在首位和链表中间设立指针——要获取中间节点位置——反转后部分链表；
* 2、分别在首尾设立指针——要获取末尾节点位置
* 问题：指针无法向前走*/

class ListNode {
    int val;
    ListNode next = null;
    ListNode prev = null;

    ListNode(int val) {
        this.val = val;
    }
//    ListNode head = null;
    //创建链表,并返回头节点
    public static ListNode creatLink(int[] num){
        ListNode Head = new ListNode(num[0]);
        ListNode cur = Head;
        for (int i = 1; i < num.length; i++) {
            ListNode listNode = new ListNode(num[i]);
            cur.next = listNode;
            listNode.prev = cur;
            cur = listNode;
        }
        return Head;
    }
}
public class PalindromeList {
    public static boolean chkPalindrome(ListNode A) {
        // write code here
        //获得中间和末尾节点位置(顺便获得链表长度？)
        ListNode last;ListNode head;
        int size = 0;
        last = A;head = A;
        while (last.next != null){//获取末尾节点位置
            size++;
            last = last.next;
        }
        if (size > 900){
            System.out.println("链表长度超过900，不合法");
            return false;
        }
        //两个指针从首尾相向而行
        while (head != last){
            if (head.val == last.val){
                head = head.next;
                last = last.prev;
            }else {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        int[] num = {421,305,13,425,222,609,100,131,579,579,131,100,609,222,425,13,305,421};
        System.out.println(PalindromeList.chkPalindrome(ListNode.creatLink(num)));
    }
}
